#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <type_traits>

namespace xsz
{
    /* ---------- 函数对象 ---------- */
    template <class T>
    class greater
    {
    public:
        bool operator()(const T &x, const T &y) const { return x > y; }
    };

    template <class T>
    class less
    {
    public:
        bool operator()(const T &x, const T &y) const { return x < y; }
    };

    /* ---------- 排序器 ---------- */
    template <class T, class Compare>
    class MySort
    {
    private:
        std::vector<T> v;
        Compare comp;

    public:
        MySort(std::vector<T> _v) : v(std::move(_v)) {}
        void quick_sort(int left, int right)
        {
            if (left >= right)
                return;
            int i = left, j = right;
            T pivot = v[(left + right) / 2];
            while (i <= j)
            {
                while (comp(v[i], pivot))
                    ++i;
                while (comp(pivot, v[j]))
                    --j;
                if (i <= j)
                {
                    std::swap(v[i], v[j]);
                    ++i;
                    --j;
                }
            }
            if (left < j)
                quick_sort(left, j);
            if (i < right)
                quick_sort(i, right);
        }
        void sort()
        {
            if (!v.empty())
                quick_sort(0, v.size() - 1);
        }
        const std::vector<T> &result() const { return v; }
    };

    /* ---------- 工具：从 cin 读 vector ---------- */
    template <class T>
    std::vector<T> readVector(std::size_t n)
    {
        std::vector<T> tmp(n);
        for (std::size_t i = 0; i < n; ++i)
            std::cin >> tmp[i];
        return tmp;
    }
} // namespace xsz